import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 深度优先搜索
 */
class SolutionDFS {
    private final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int numIslands(char[][] grid) {
        int h = grid.length, w = grid[0].length;
        boolean[][] visited = new boolean[h][w];
        int ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (grid[i][j] == '0' || visited[i][j]) {
                    continue;
                }
                dfs(grid, visited, i, j);
                ans++;
            }
        }

        return ans;
    }

    private boolean isValidPos(char[][] grid, int i, int j) {
        int h = grid.length, w = grid[0].length;
        return i >= 0 && i < h && j >= 0 && j < w;
    }

    private void dfs(char[][] grid, boolean[][] visited, int i, int j) {
        visited[i][j] = true;
        for (int[] dir : DIRS) {
            int nextI = i + dir[0];
            int nextJ = j + dir[1];
            if (isValidPos(grid, nextI, nextJ) && grid[nextI][nextJ] == '1' && !visited[nextI][nextJ]) {
                dfs(grid, visited, nextI, nextJ);
            }
        }
    }
}

/**
 * 广度优先搜索
 */
class SolutionBFS {

    private final int[][] DIRS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    static class P {
        int i, j;

        P(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    public int numIslands(char[][] grid) {
        int h = grid.length, w = grid[0].length;
        boolean[][] visited = new boolean[h][w];
        int ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (grid[i][j] == '0' || visited[i][j]) {
                    continue;
                }
                bfs(grid, visited, new P(i, j));
                ans++;
            }
        }
        return ans;
    }

    private boolean isValidPos(char[][] grid, int i, int j) {
        int h = grid.length, w = grid[0].length;
        return i >= 0 && i < h && j >= 0 && j < w;
    }

    private void bfs(char[][] grid, boolean[][] visited, P initP) {
        visited[initP.i][initP.j] = true;
        Queue<P> queue = new ArrayDeque<>();
        queue.offer(initP);
        while (!queue.isEmpty()) {
            P p = queue.poll();
            for (int[] dir : DIRS) {
                P nextP = new P(p.i + dir[0], p.j + dir[1]);
                if (isValidPos(grid, nextP.i, nextP.j) && grid[nextP.i][nextP.j] == '1' && !visited[nextP.i][nextP.j]) {
                    queue.offer(nextP);
                    visited[nextP.i][nextP.j] = true;
                }
            }
        }

    }
}

class Solution extends SolutionDFS {}

public class Main {
    public static void main(String[] args) {
        final char[][] grid = {
                {'1', '1', '1', '1', '0'},
                {'1', '1', '0', '1', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0'}
        };
        System.out.println(new SolutionBFS().numIslands(grid));
    }
}